package bishi.tengxun.three;


/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/09/26 21:09
 */
public class four {
    public static void main(String[] args) {
        four f = new four();
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left = new TreeNode(10);
        root.left.right = new TreeNode(9);
        root.left.left = new TreeNode(7);
        root.left.left.left = new TreeNode(5);
        root.left.left.right = new TreeNode(4);
        root.left.left.right.right = new TreeNode(3);
        root.left.left.right.left = new TreeNode(8);
        root.left.left.right.right.left = new TreeNode(6);
        f.solve(root, new int[][]{{8, 3}, {5, 6}, {4, 5}, {2, 7}});
        System.out.println(123);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode solve(TreeNode root, int[][] b) {
        // write code here
        for (int[] nums : b) {
            Swap[] swaps = new Swap[2];
            if (dfsSwap(root, nums[0], nums[1], swaps)) {
                if (swaps[1].root == swaps[0].root) {
                    continue;
                }
                TreeNode node1;
                if (swaps[0].left) {
                    node1 = swaps[0].root.left;
                } else {
                    node1 = swaps[0].root.right;
                }
                if (swaps[1].left) {
                    if (swaps[0].left) {
                        swaps[0].root.left = swaps[1].root.left;
                        swaps[1].root.left = node1;
                    } else {
                        swaps[0].root.right = swaps[1].root.left;
                        swaps[1].root.left = node1;
                    }
                } else {
                    if (swaps[0].left) {
                        swaps[0].root.left = swaps[1].root.right;
                        swaps[1].root.right = node1;
                    } else {
                        swaps[0].root.right = swaps[1].root.right;
                        swaps[1].root.right = node1;
                    }
                }

            }
        }
        return root;
    }

    class Swap {
        boolean left;
        TreeNode root;

        Swap(TreeNode root, boolean left) {
            this.left = left;
            this.root = root;
        }
    }

    public boolean dfsSwap(TreeNode root, int a, int b, Swap[] swaps) {
        if (root.left != null) {
            if (root.left.val == a) {
                swaps[0] = new Swap(root, true);
            } else if (root.left.val == b) {
                swaps[0] = new Swap(root, true);
            }
        }
        if (root.right != null) {
            if (root.right.val == a) {
                swaps[1] = new Swap(root, false);
            } else if (root.right.val == b) {
                swaps[1] = new Swap(root, false);
            }
        }
        if (swaps[0] != null && swaps[1] != null) return true;
        boolean left = false;
        boolean right = false;
        if (root.left != null && root.left.val != a && root.left.val != b) left = dfsSwap(root.left, a, b, swaps);
        if (left) return left;
        if (root.right != null && root.right.val != a && root.right.val != b) right = dfsSwap(root.right, a, b, swaps);
        return right;
    }
}
